//: [Previous](@previous)
import Foundation

/*:
 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

 输入：nums = [0,1,0,3,2,3]
 输出：4

 输入：nums = [7,7,7,7,7,7,7]
 输出：1

 进阶：
 你可以设计时间复杂度为 O(n2) 的解决方案吗？
 你能将算法的时间复杂度降低到 O(n log(n)) 吗?
 */

/*:
 动态规划
 1,n=1
 max(1+dp[j]|j<-0..<n),n>1
 */

func lengthOfLIS(_ nums: [Int]) -> Int {
    var dp: [Int] = Array(repeating: 1, count: nums.count)

    for i in 1..<dp.count {
        for j in 0..<i {
            if nums[i] > nums[j] {
                dp[i] = max(dp[i], 1 + dp[j])
            }
        }
    }

    var res = 0
    for i in 0..<dp.count {
        res = max(res, dp[i])
    }
    return res
}

print(lengthOfLIS([0,1,0,3,2,3]))
print(lengthOfLIS([7,7,7,7,7,7,7]))

/*:
 二分查找算法 纸牌算法
 */
func lengthOfLIS2(_ nums: [Int]) -> Int {
    var top: [Int] = Array(repeating: 0, count: nums.count)
    // 牌堆数初始化为 0
    var piles = 0
    for i in 0..<nums.count {
        // 要处理的扑克牌
        var poker = nums[i]

        // 搜索左侧边界的二分查找
        var left = 0, right = piles
        while left < right {
            let mid = (left + right) / 2
            if (top[mid] > poker) {
                right = mid
            } else if top[mid] < poker {
                left = mid + 1
            } else {
                right = mid
            }
        }

        // 没找到合适的牌堆，新建一堆
        if left == piles {
            piles += 1
        }
        // 把这张牌放到牌堆顶
        top[left] = poker
    }

    // 牌堆数就是 LIS ⻓度
    return piles
}

print(lengthOfLIS2([0,1,0,3,2,3]))
print(lengthOfLIS2([7,7,7,7,7,7,7]))

//: [Next](@next)
